package com.test.daily.leetcode.y2022.m05.day0526.v06;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/26 下午 11:51
 * @version: 1.0
 */
public class Solution {
    public static int islandNums(char[][] boards) {
        int islands = 0;
        for (int i = 0; i < boards.length; i++) {
            for(int j = 0; j < boards[0].length; j++){
                if(boards[i][j] == '1'){
                    infect(boards, i, j);
                    islands++;
                }
            }
        }
        return islands;
    }

    public static void infect(char[][] board, int i, int j) {
        if (i < 0 || i == board.length || j < 0 || j == board[0].length || board[i][j] != '1') {
            return;
        }
        board[i][j] = '0';
        infect(board, i - 1, j);
        infect(board, i + 1, j);
        infect(board, i, j - 1);
        infect(board, i, j + 1);
    }
    public static class Node<T>{
        T t;
        public Node(T t){
            this.t = t;
        }
    }
    public static class Dot{}

    public static class UnionFind<T>{
        HashMap<T, Node> nodes;
        HashMap<Node, Node> parentMap;
        HashMap<Node, Integer> sizeMap;
        public UnionFind(List<T> list){
            for (int i = 0; i < list.size(); i++) {
                Node node = new Node(list.get(i));
                nodes.put(list.get(i), node);
                parentMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }
        public Node findFather(Node cur){
            Stack<Node> stack = new Stack<>();
            while (cur != parentMap.get(cur)){
                stack.push(cur);
                cur = parentMap.get(cur);
            }
            while(!stack.isEmpty()){
                parentMap.put(stack.pop(), cur);
            }
            return cur;
        }
         
    }
}
